package problem32;

//32.最长有效括号
//https://leetcode.cn/problems/longest-valid-parentheses/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int[] dp = new int[n];
        int ret = 0;
        for(int i = 1; i<n; i++) {
            char ch = s.charAt(i);
            if(ch == ')') {
                if(s.charAt(i-1) == '(') {
                    if(i - 2 >= 0) dp[i] = dp[i-2] + 2;
                    else dp[i] = 2;
                }else if(i - dp[i - 1] -1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    if(i-dp[i-1]-2 >= 0) {
                        dp[i] = dp[i-dp[i-1]-2] + dp[i-1] + 2;
                    }else {
                        dp[i] = dp[i-1] + 2;
                    }
                }
            }
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }
}

/**

dp[i]: 以第i个括号为结尾的最长有效括号长度

 */